package 数据结构专栏.C_排序算法.training;

import java.util.Arrays;

public class Test_20240321 {
    public static void main(String[] args) {
        // 构造乱序数组
        int[] arr = new int[]{10, 2, 5, 8, 1, 3, 4, 7, 6, 9};

        int[] arr0 = Arrays.copyOf(arr, arr.length);
        insertSort(arr0);
        System.out.println("insertSort:" + printArray(arr0));

        int[] arr1 = Arrays.copyOf(arr, arr.length);
        bubbleSort(arr1);
        System.out.println("bubbleSort:" + printArray(arr1));

        int[] arr2 = Arrays.copyOf(arr, arr.length);
        selectSort(arr2);
        System.out.println("selectSort:" + printArray(arr2));


        int[] arr3 = Arrays.copyOf(arr, arr.length);
        quickSort(arr3, 0, arr.length - 1);
        System.out.println("quickSort:" + printArray(arr3));


//        int[] arr4 = Arrays.copyOf(arr, arr.length);
//        mergeSort(arr4, 0, arr.length - 1);
//        System.out.println("mergeSort:" + printArray(arr4));

        int[] arr5 = Arrays.copyOf(arr, arr.length);
        heapSort(arr5);
        System.out.println("heapSort:" + printArray(arr5));

    }

    private static String printArray(int[] arr) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i] + " ");
        }
        return sb.toString();
    }

    // 插入排序
    // 复杂度：
    // 简单的排序算法，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }

    // 编写冒泡排序
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // 编写选择排序:
    // 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }


    // 编写快速排序
    // 分而治之的算法。选取一个元素作为"基准"（pivot），通过一趟排序将待排序列分割成独立的两部分，其中一部分的所有元素都比另一部分的所有元素要小。然后再按此方法对这两部分分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            quickSort(array, low, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, high);
        }
    }

    public static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = (low - 1);
        for (int j = low; j <= high - 1; j++) {
            if (array[j] < pivot) {
                i++;
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;
        return i + 1;
    }

    // 编写归并排序
    // 建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行
    public static void mergeSort(int[] array, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            mergeSort(array, low, mid);
            mergeSort(array, mid + 1, high);
            merge(array, low, mid, high);
        }
    }

    public static void merge(int[] array, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= high) {
            if (array[i] < array[j]) {
                temp[k++] = array[i++];
            }
        }
    }

    // 编写堆排序
    // 堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点
    public static void heapSort(int[] array) {
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            heapify(array, array.length, i);
        }
        for (int i = array.length - 1; i >= 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            heapify(array, i, 0);
        }
    }

    public static void heapify(int[] array, int heapSize, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < heapSize && array[left] > array[largest]) {
            largest = left;
        }
        if (right < heapSize && array[right] > array[largest]) {
            largest = right;
        }
        if (largest != i) {
            int swap = array[i];
            array[i] = array[largest];
            array[largest] = swap;
            heapify(array, heapSize, largest);
        }
    }

}
